package com.seven.leetcode.problems;

/**
 * 5. 最长回文子串
 * LongestPalindromicSubstring
 * https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
 * 级别：Medium
 * <p>
 * 给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
 * <p>
 * 示例 1：
 * <p>
 * 输入: "babab"   aabb
 * 输出: "bab"
 * 注意: "aba" 也是一个有效答案。
 * 示例 2：
 * <p>
 * 输入: "cbbd"
 * 输出: "bb"
 * <p>
 * 输入：s = "a"
 * 输出："a"
 * <p>
 * 输入：s = "ac"
 * 输出："a"
 * <p>
 * 输入：s = "ccc"
 * 输出："ccc"
 * <p>
 * 输入：s = "aacabdkacaa"
 * 输出："aca"
 *
 * @author : wenguang
 * @date : 2021/3/22 11:03
 */
public class LongestPalindromicSubstring {

    public static void main(String[] args) {
        String in = "aacabdkacaa";
        System.out.println("in: " + in);
        String out = longestPalindromicSubstring1(in);
        System.out.println("out: " + out);
    }

    public static String longestPalindromicSubstring1(String s) {
        if (s == null || s.length() < 1) {
            return "";
        }

        // 初始化最大回文子串的起点和终点
        int start = 0;
        int end = 0;

        // 遍历每个位置，当做中心位
        for (int i = 0; i < s.length(); i++) {
            // 分别拿到奇数偶数的回文子串长度
            int lenOdd = expandCenter(s, i, i);
            int lenEven = expandCenter(s, i, i + 1);
            // 对比最大的长度
            int len = Math.max(lenOdd, lenEven);
            // 计算对应最大回文子串的起点和终点
            if (len > end - start) {
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }
        // 注意：这里的end+1是因为 java自带的左闭右开的原因
        return s.substring(start, end + 1);
    }


    /**
     * @param s     输入的字符串
     * @param left  起始的左边界
     * @param right 起始的右边界
     * @return 回文串的长度
     */
    private static int expandCenter(String s, int left, int right) {
        // left = right 的时候，此时回文中心是一个字符，回文串的长度是奇数
        // right = left + 1 的时候，此时回文中心是一个空隙，回文串的长度是偶数
        // 跳出循环的时候恰好满足 s.charAt(left) ！= s.charAt(right)
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        // 回文串的长度是right-left+1-2 = right - left - 1
        return right - left - 1;
    }

    /**
     * 超时
     *
     * @param s
     * @return
     */
    public static String longestPalindromicSubstring2(String s) {
        if (null == s || s.length() <= 1) {
            return s;
        }

        int start = 0;
        int end = 0;
        StringBuilder builder = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            char c1 = s.charAt(i);
            for (int j = s.length() - 1; j > i; j--) {
                char c2 = s.charAt(j);
                if (c1 == c2) {
                    int idx = (i + j) / 2;
                    String s1 = s.substring(i, idx + 1);
                    String s2;
                    if ((j - i) % 2 == 0) {
                        s2 = s.substring(idx, j + 1);
                    } else {
                        s2 = s.substring(idx + 1, j + 1);
                    }

                    builder.delete(0, builder.length());
                    if (s1.equals(builder.append(s2).reverse().toString())) {
                        if (j - i > end - start) {
                            start = i;
                            end = j;
                        }
                    }
                }
            }
        }

        return s.substring(start, end + 1);
    }
}
